package 剑指offer;


/**
 * @author: tyy 剑指 Offer
 * 230. 二叉搜索树中第K小的元素
 *给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
    示例 1：
    输入：root = [3,1,4,null,2], k = 1
    输出：1
 * @create: 2021-10-14 17:40
 * @description:
 **/
public class Solution3 {
    /**
     * 查找左子树节点个数为leftN,如果K<=leftN,则所查找节点在左子树上.
     * 若K=leftN+1,则所查找节点为根节点
     * 若K>leftN+1,则所查找节点在右子树上,按照同样方法查找右子树第K-leftN个节点
     *
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        int leftN = findChild(root.left);
        if (leftN + 1 == k) return root.val;
        else if (k <= leftN) {
            return kthSmallest(root.left, k);
        } else return kthSmallest(root.right, k - leftN - 1);
    }

    /**
     * 查找子节点个数
     *
     * @param root
     * @return
     */
    public int findChild(TreeNode root) {
        if (root == null) return 0;
        return findChild(root.left) + findChild(root.right) + 1;
    }

    public static void main(String[] args) {

    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}


